#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef char ElemType;

// FUNCTION: 定义线索二叉树结点结构
typedef struct ThreadNode {
	ElemType data;
	struct ThreadNode *lchild, *rchild;
	// HINT: 我们不如将其称之为：线索使能标记位（类似于数电的知识。1为有效，0为无效）
	int ltag, rtag;
} ThreadNode, *ThreadTree;


// FUNCTION: 手工建树，总计5个结点
void BulidThreadTree(ThreadTree &T) {
	ThreadTree arr[5];
	int i;

	// NOTE: 创建树结点
	for (i = 0; i < 5; i++) {
		arr[i] = (ThreadTree) malloc(sizeof(ThreadNode));
		memset(arr[i], 0, sizeof(ThreadNode));
		arr[i]->data = 'A' + i;
	}

	// NOTE: 建立树状关系
	arr[0]->lchild = arr[1];
	arr[0]->rchild = arr[2];
	arr[1]->rchild = arr[3];
	arr[2]->lchild = arr[4];

	T = arr[0];
}


// BUNDLE: 构建线索二叉树——用递归的方式进行中序线索化
// NOTE: 定义全局变量pre，指向当前访问结点的前驱
ThreadNode *pre = NULL;

// FUNCTION: 实现对结点的线索的构建
void visit(ThreadNode *q) {
	// STEP: q指针所指结点的左子树为空，建立前驱线索
	if (q->lchild == NULL) {
		q->lchild = pre;
		q->ltag = 1;
	}

	// STEP: q指针所指结点的右子树为空，建立后继线索
	if (pre != NULL && pre->rchild == NULL) {
		q->rchild = q;
		q->rtag = 1;
	}

	// STEP: 指向前驱的pre指针步进到q
	pre = q;
}

// FUNCTION: 控制遍历走向
void InThread(ThreadTree T) {
	if (T != NULL) {
		// STEP: 递归找当前结点的左孩子
		InThread(T->lchild);

		// STEP: 访问根结点
		visit(T);

		// STEP: 递归找当前结点的右孩子
		InThread(T->rchild);
	}
}


// FUNCTION: 实现对二叉树的中序线索化函数
void CreateInThread(ThreadTree T) {
	// NOTE: 使用辅助指针pre
	ThreadTree pre = NULL;

	// NOTE: 对于非空二叉树才能实现线索化
	if (T != NULL) {
		// STEP: 构建中序线索二叉树
		InThread(T);

		// STEP: 额外处理中序线索二叉树的最后一个结点
		if (pre->rchild == NULL) {
			pre->rtag = 1;
		}
	}
}






/*
// NOTE: 不理解直接放弃
void InThread(ThreadTree &p, ThreadTree &pre) {
	// 当前树根是否不为NULL？
	if (p != NULL) {
		// 递归找树的左孩子
		InThread(p->lchild, pre);

		// 左边为NULL,填写当前结点的前驱
		if (p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = 1;
		}

		// pre节点右孩子为NULL，就让其指向后继节点，而后继结点刚好就是p
		if (pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = 1;
		}


		pre = p;

		InThread(p->rchild, pre);
	}
}

// FUNCTION: 构建线索二叉树
void CreateInThread(ThreadTree T) {
	// NOTE: 使用辅助指针pre
	ThreadTree pre = NULL;
	if (T != NULL) {
		// 不断递归找树的左孩子
		InThread(T, pre);
		pre->rchild = NULL;
		pre->rtag = 1;
	}
}
*/

//中序序列下的第一个结点
// ThreadNode *Firstnode(ThreadNode *p) {
// 	while (p->ltag == 0)
// 		p = p->lchild;
// 	return p;
// }

//p在中序序列下的后继结点
//《王道C督学营》课程，考研没考过大题，主要是实际没应用场景
int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	// STEP: 结构体指针变量——指向临时创建的结点
	ThreadTree T;
	ThreadTree p;

	// NOTE: 构建二叉树
	BulidThreadTree(T);

	// NOTE: 线索化二叉树
	CreateInThread(T);

	// NOTE: 找到中序遍历的第一个元素
	p = Firstnode(T);
	printf("最左下结点值为 %c\n", p->data);

	return 0;
}